package leetcode;

import java.util.Arrays;

//According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers 
//have at least h citations each, and the other N − h papers have no more than h citations each."

//For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and 
//each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with 
//at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

public class HIndex {

	public static void main(String[] args) {
		HIndex hIndex = new HIndex();
		int[] citations = {0,0,0,0};
		System.out.println(hIndex.hIndex2(citations));
	}
	public int hIndex(int[] citations) {
		if (citations == null || citations.length == 0)
			return 0;
		Arrays.sort(citations);
		final int N = citations.length;
		////影响HIndex的有两个瓶颈，一个是论文的数量，一个是论文的引用数
		//这个的思想也是当瓶颈发生变化时，之后的值再也不可能比当前值大了，只不过是论文的数量
		//由于我们是从大到小计算的，刚开始的瓶颈是论文的数量，比如在12时是 10篇大于等于12的
		for (int i = 0; i < N; i++) {
			if (N - i <= citations[i])
				return N - i;
		}
		return 0;
	}

	public int hIndex2(int[] citations) {
		if (citations == null || citations.length == 0)
			return 0;
		Arrays.sort(citations);
		final int length = citations.length;
		//就是找到一个值，小于这个值的论文引用数最多是N - h，大于等于该值的最少是h篇,后来发现错了，不是找值，是找篇数
        //因为H ： 0 ~ N
        //找到i值，大于等于citation[i]的篇数是length - i，使得它的数目大于等于citation[i]
		for (int i = length - 1; i >= 0; i--) {
			// 比如1 4 6 8 9 12 15...(15篇，有10篇大于10的)
			
			//影响HIndex的有两个瓶颈，一个是论文的数量，一个是论文的引用数
			//这个的思想就是当瓶颈发生变化时，之后的值再也不可能比当前值大了
			//由于我们是从大到小计算的，刚开始的瓶颈是论文的数量，比如在12时是 10篇大于等于12的
			//但是后来的论文引用数下降，则此时会成为新的瓶颈，而一旦论文引用数成为瓶颈，之前的引用数都小于该引用数
			//所以不会有更大的HIndex了
			if (citations[i] < length - i) {
				return length - 1 - i;
			}
			//其实这个的思路最简单，curHIndex 总是取两者中的最小值，然后更新res
			// curH = Math.min(citations[i], length - i);
			// res = Math.max(res, curH);
		}
		// 比如 4 6 8 9会返回4
		return length;
	}
}
